package 数据结构.章节09;

/**
 * @author 挚爱之夕
 * @date 2021/10/12 - 10 - 12 - 18:39
 * @Description: 数据结构.章节09
 * @Version: 1.0
 */
public class _156_链表加法 {

    public static void main(String[] args) {
        int[] a = new int[]{6, 4, 3, 8, 1};
        int[] b = new int[]{6, 2, 7, 3};
        Node headA = new Node(a[0]);
        Node headB = new Node(b[0]);
        Node p = headA;
        for (int i = 1; i < a.length; i++) {
            p.next = new Node(a[i]);
            p = p.next;
        }
        p = headB;
        for (int i = 1; i < b.length; i++) {
            p.next = new Node(b[i]);
            p = p.next;
        }
        p = headA;
        while (p != null) {
            System.out.print(p.val + "\t");
            p = p.next;
        }
        System.out.println();
        p = headB;
        while (p != null) {
            System.out.print(p.val + "\t");
            p = p.next;
        }
        System.out.println();
        p = plusAB(headA, headB, 0);
        while (p != null) {
            System.out.print(p.val + "\t");
            p = p.next;
        }

    }

    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    /*
    递归：调用时i赋值为0，i表示进位
     */
    private static Node plusAB(Node a, Node b, int i) {
        if (a == null && b == null && i == 0)
            return null;
        int val = i;
        if (a != null)
            val += a.val;
        if (b != null)
            val += b.val;
        Node result = new Node(val % 10);
        result.next = plusAB(a == null || a.next == null ? null : a.next,
                b == null || b.next == null ? null : b.next,
                val >= 10 ? 1 : 0);
        return result;
    }
}
